package 分治快排;

import java.awt.font.NumericShaper;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

public class 数组中的第K个最大元素3 {
    //找第k大元素
    //https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
    public int findKthLargest1(int[] nums, int k) {
        // 堆排序：第k大、第k小、前k大、前k小
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> (Integer) o2 - (Integer) o1);
        for (int x : nums) {
            priorityQueue.offer(x);
        }
        for (int i = 0; i < k - 1; i++) {
            priorityQueue.poll();
        }
        return priorityQueue.poll();
    }
    public static int findKthLargest2(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, k);
    }
    public static int find(int[] nums, int l, int r, int k) {
        int left = l - 1, right = r + 1, cur = l, rand = nums[new Random().nextInt(r - l + 1) + l];
        while(cur < right) {
            if(nums[cur] < rand) swap(nums,++left,cur++);
            else if(nums[cur] == rand) cur++;
            else swap(nums,--right,cur);
        }
        if(r - right + 1 >= k) return find(nums,right,r,k);
        else if(r - left >= k) return /*nums[left + 1]*/ rand;
        else return find(nums, l, left, k - (r - left));
    }

    //找元素(第k大)
    public int findKthLargest(int[] nums, int k) {
        return qfind(nums, 0, nums.length - 1, k);
    }
    public int qfind(int[] nums, int l, int r, int k) {
        if(l == r) return nums[l]; // l == r一个元素 此时的第k==1大 就是它
        // 上层r < l 或 l > r时递归不进来的，在上面两个if判定中就进去了，不会进递归的if而非法调用
        // l > r 找的区间都是合法的，相等时也退 不会接下来的非法

        int key = nums[new Random().nextInt(r - l + 1) + l];

        // 三指针的基准排序 排好三块：[无序的左小块]、[排好的块等元素]、[无序的右大块]
        int left = l - 1, right = r + 1, cur = l;
        while(cur < right) {
            if(nums[cur] < key) swap(nums, ++left, cur++);
            else if(nums[cur] == key) cur++;
            else swap(nums,--right,cur);
        }

        // 快速选择找元素(找第k大元素)
        // [l, left]、[left + 1, right - 1]、[right, r]
        int b = right - left - 1, c = r - right + 1; // 中间块元素个数、右块元素个数
        // 有左区间为0 左指针没动 即left = l - 1 与 右区间为0 右指针没动 即right = r + 1，这些非法的 去递归传 会越界情况，但在这里不会进
        if(c >= k) return qfind(nums, right, r, k); // a区间0元素，b+c=数组长度,k<=数组元素个数，如果进第一个if，传右区间的 没有递归传 非法越界的l 与 left = l - 1，如果进第二个if，没有递归调用b+c一定>=k
        else if(b + c >= k) return key; // c区间为0元素，0一定<k,第一个if一定不会进，第二个if进没事，第三个if 传的是左区间的，不传非法的右区间
        else return qfind(nums, l, left, k - b - c); // 因此递归进来的时候 不用判断l与r大小 非法的都是过不来的
    }
    public static void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    public static void main(String[] args) {
        System.out.println(findKthLargest2(new int[] {3,2,3,1,2,4,5,5,6},4));
    }
}
